// https://leetcode.cn/problems/clone-graph/
// Created by ade on 2022/7/26.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node {
public:
    int val;
    vector<Node *> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node *>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node *>();
    }

    Node(int _val, vector<Node *> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};


class Solution {
public:
    Node *cloneGraph(Node *node) {
        if(!node) return nullptr;
        return dfs(node);
    }

    unordered_map<Node *, Node *> nodeMap; // old -> new
    Node * dfs(Node *old) {
        if (nodeMap.find(old) != nodeMap.end()) {
            return nodeMap[old];
        }
        Node * n = new Node(old->val);
        nodeMap[old] = n;
        for(auto i : old->neighbors){
            Node * newNb = dfs(i);
            n->neighbors.push_back(newNb);
        }
        return n;
    }

    Node *init() {
        Node *n1 = new Node(1);
        Node *n2 = new Node(2);
        Node *n3 = new Node(3);
        Node *n4 = new Node(4);
        n1->neighbors = {n2, n4};
        n2->neighbors = {n1, n3};
        n3->neighbors = {n2, n4};
        n4->neighbors = {n1, n3};
        return n1;
    }

    unordered_map<Node *, int> myMap;

    void show(Node *node) {
        if (myMap.find(node) == myMap.end()) {
            cout << "node:" << node->val << ",neighbours:";
            auto neighbours = node->neighbors;
            for (auto n : neighbours) {
                cout << n->val << ",";
            }
            cout << endl;
            myMap[node] = 1;

            for (auto n : neighbours) {
                show(n);
            }
        }

    }
};

int main() {
    Solution so;
    Node *n1 = so.init();
//    so.show(n1);
    Node *newNode = so.cloneGraph(n1);
    so.show(newNode);
    return 0;
}

